package graph

import (
  "container/list";
  "os";
  "fmt";
)

// constants to limit resource use and prevent
// hanging in the event of a logic error
const (
  BFS_MAXPATH = 100;
  BFS_MAXSEARCHITER = 100;
)

// searches for the named vertex using Breadth-First Search algorithm
func (g *Graph) DoBfs (s string) {
  dbg("Searching for ",s);
  searchVertex := g.GetVertex(s);
  searchVertex.Bfs = newBfsBarn();
  searchVertex.Bfs.Dist = 0;
  
  l := list.New();
  _ = l.PushBack(searchVertex);
  
  dbg("searchVertex ",searchVertex);
  e := l.Front();
  // two things here:
  // 1. e may be nil and we can still cast it to a Vertex, that's fine.
  // 2. we reassign n later, here we're doing an extra assignment just
  // to get into the loop.
  //n := e.Value.(*Vertex);
  abortCheck := 1;
  for ; e != nil ; {
    // queue adjacent vertices
    n := e.Value.(*Vertex);
    if abortCheck > BFS_MAXSEARCHITER {
      os.Exit(EXIT_EXCEEDED_SEARCHITER);
    }
    abortCheck++;
    dbg(n);
    for k,v := range(n.Adjacent) {
      //increase the recorded path length for each vertex
      // not yet visted and record it for a later visit
      if v.Bfs == nil {
        dbg("found ",k);
        v.Bfs = newBfsBarn();
        v.Bfs.Dist = n.Bfs.Dist+1;
        v.Bfs.Prev = n;
        dbg("k ",k," dist ",v.Bfs.Dist," prev",v.Bfs.Prev);
        if v.Bfs.Dist > BFS_MAXPATH {
          os.Exit(EXIT_EXCEEDED_MAXPATH);
        }
        l.PushBack(v);
      }
    }
    e = e.Next();
  }
}

func (g *Graph) GetBfsResults() (s string) {
  s = "Paths for " + g.Name + "\n";
  for vname, v := range g.vertexMap {
    dist := v.Bfs.Dist;
    s += fmt.Sprintf("%s: ",vname);
    for v.Bfs.Prev != nil {
      s += fmt.Sprintf(" %s ", v.Bfs.Prev.Name);
      v = v.Bfs.Prev;
    }
    s += fmt.Sprintf(" total %d\n", dist);
  }
  return;
}

